package BFS;

import 其他.DataStructure.TreeNode;
import org.junit.Test;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * 广搜模板题
 *
 * ~ 迭代 中序 队列 混乱？
 */
public class 二叉树的最小深度111 {

    public int minDepth(TreeNode root) {
        int resMinDepth = 0;
        if (root == null) {
            return resMinDepth;
        }

        // 队列 去重
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Set<TreeNode> visit = new HashSet<>();

        // 放入根节点
        nodeQueue.offer(root);
        visit.add(root);
        resMinDepth = 1;

        // BFS
        while (!nodeQueue.isEmpty()) {
            // 暂存size，因为不能用动态的que.size
            int oldSize = nodeQueue.size();

            // 遍历old
            for (int i = 0; i < oldSize; i++) {
                TreeNode cur = nodeQueue.poll(); // poll 弹出并返回
                // 看是否 已找到目标点
                if (cur.left == null && cur.right == null) {
                    return resMinDepth;
                }
                // 放入四周节点     （注意 fori 遍历的还是 老old的，不冲突~）
                if (cur.left != null) {
                    nodeQueue.offer(cur.left);
                }
                if (cur.right != null) {
                    nodeQueue.offer(cur.right);
                }
            }
            resMinDepth++; // 每层 深度 +1
        }
        return resMinDepth;
    }

    @Test
    public void test() {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(7);
        TreeNode t3 = new TreeNode(-10);
        TreeNode t4 = new TreeNode(-2);
        TreeNode t5 = new TreeNode(3);
        TreeNode t6 = new TreeNode(1);
        TreeNode t7 = new TreeNode(2);
        TreeNode t8 = new TreeNode(1);
        TreeNode t9 = new TreeNode(4);
        t1.left = t2;
        t1.right = t3;
        t2.left = t4;
        t3.left = t5;
        t3.right = t6;
        t5.left = t7;
        t5.right = t8;
        t8.right = t9;
        System.out.println("res:" + minDepth(t1));
    }
}
